from SStack import *
from SQueue import *

maze1 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
    [1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def mark(maze, pos):
    maze[pos[0]][pos[1]] = 2


def passable(maze, pos):
    return maze[pos[0]][pos[1]] == 0

############################################
########## A recursive maze path finder ####


def maze_solver_rec(maze, start, end):
    """ A maze solver using a recursive procedure to find the path.
    """
    def find_path(maze, start, end):
        mark(maze, start)
        if start == end:
            print(start, end=' ')
            return True
        for i in range(4):
            nextp = start[0] + dirs[i][0], start[1] + dirs[i][1]
            if passable(maze, nextp):
                if find_path(maze, nextp, end):
                    print(start, end=' ')
                    return True
        return False

    print("If find, print the path from end to start:")
    if find_path(maze, start, end):
        print("\n")
    else:
        print("No path exists.")
# end maze_solver_rec


##################################################
####### A non-recursive maze path finder #########
####### which use a stack as temprary storage ####

def print_path(end, last, st):
    print(end, last, sep=" ", end=' ')
    while not st.is_empty():
        print(st.pop()[0], end=' ')
    print('\n')


def print_path_rev(end, last, st):  # print the path from start to end
    path = [end, last]
    while not st.is_empty():
        path.append(st.pop())
    path.reverse()
    for pos in path:
        print(pos, end=" ")
    print('\n')


def maze_solver(maze, start, end):
    if start == end:
        print(start)
        return
    st = SStack()
    mark(maze, start)
    st.push((start, 0))         # start position into stack
    while not st.is_empty():    # have possibility to try
        pos, nxt = st.pop()     # get last branch position
        for i in range(nxt, 4):  # try to find unexploring dir(s)
            nextp = (pos[0] + dirs[i][0], pos[1] + dirs[i][1])  # next point
            if nextp == end:        # find end, great! :-)
                print_path(end, pos, st)
                return
            if passable(maze, nextp):  # new position is passable
                st.push((pos, i + 1))  # original position in stack
                mark(maze, nextp)
                st.push((nextp, 0))  # new position into stack
                break
    print("No path.")  # :-(

####### Search a maze using a queue ##############
####### No path record ###########################


def maze_solver_queue(maze, start, end):
    if start == end:
        print("Path finds.")
        return
    qu = SQueue()
    mark(maze, start)
    qu.enqueue(start)        # start position into queue
    while not qu.is_empty():  # have possibility to try
        pos = qu.dequeue()   # take next try position
        for i in range(4):   # chech each direction
            nextp = (pos[0] + dirs[i][0],
                     pos[1] + dirs[i][1])  # next position
            if passable(maze, nextp):     # find new position
                if nextp == end:          # end position, :-)
                    print("Path finds.")   # where is the path??
                    return
                mark(maze, nextp)
                qu.enqueue(nextp)         # new position into queue
    print("No path.")  # :-(

####### Search a maze using a queue ###############
####### recording the path precedent relation #####


def build_path(start, pos, end, precedent):
    path = [end]
    while pos != start:
        path.append(pos)
        pos = precedent[pos]
    path.append(start)
    path.reverse()
    return path


def maze_solver_queue1(maze, start, end):
    if start == end:
        return [start]
    qu = SQueue()
    precedent = dict()
    mark(maze, start)
    qu.enqueue(start)        # start position into queue
    while not qu.is_empty():  # have possibility to try
        pos = qu.dequeue()   # take next try position
        for i in range(4):   # chech each direction
            nextp = (pos[0] + dirs[i][0],
                     pos[1] + dirs[i][1])  # next position
            if passable(maze, nextp):     # find new position
                if nextp == end:         # end position, :-)
                    return build_path(start, pos, end, precedent)
                mark(maze, nextp)
                precedent[nextp] = pos    # set precedent of nextp
                qu.enqueue(nextp)         # new position into queue
    print("No path.")  # :-(

# Another implementation using a stack.
# A pos and a stack hold the information used in searching.
# It seems that this implementation is not really better,
# not clearer, nor shorter, nor conceptly better.


def print_path1(end, st):
    print(end, end=' ')
    while not st.is_empty():
        print(st.pop()[0], end=' ')
    print('\n')


def maze_solver1(maze, start, end):
    st = SStack()
    pos, nxt = start, 0
    while True:
        if pos == end:
            print_path1(pos, st)
            return
        mark(maze, pos)
        for i in range(nxt, 4):  # 依次检查潜在探索方向
            nextp = (pos[0] + dirs[i][0],
                     pos[1] + dirs[i][1])  # 算出下一点
            if passable(maze, nextp):  # 遇到未探查点
                st.push((pos, i + 1))   # 原位置进栈
                pos, nxt = nextp, 0
                break
        else:
            if st.is_empty():
                break
            pos, nxt = st.pop()
    print("No path found.")  # 找不到路径
# end of maze_solver


if __name__ == "__main__":
    #    maze_solver_rec(maze1, (1,1), (18,18))
    #    maze_solver1(maze1, (1,1), (18,18))

    #    maze_solver_queue(maze1, (1,1), (18,18))
    #    print(maze_solver_queue1(maze1, (1,1), (18,18)))
